package tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

/**
 * 孩子链表建立树,并输出任一种遍历序列检查所建树的正确性
 * */
public class ChildrenTree<AnyType> {
	int n, root, parent, child;
	PTListNode<AnyType> rootNode;
	CTNode<AnyType> firstChild;
	PTListNode[] nodes ;


	ChildrenTree() {
		rootNode = null;
		n = 0;
	}

	/**先根遍历
	 * */
	public void preOrder(){
		
	}
	public void preOrder(PTListNode[] nodes){
		CTNode<AnyType> node=nodes[0].firstChild;
		while(node!=null){
		}
	}
	
	/**层次遍历
	 * */
	public List<Integer> levelOrder(PTListNode[] nodes){
		List<Integer> list = new ArrayList<Integer>();
		//加入根结点
		list.add(0);
		for(int i=0;i<n;i++){
			CTNode<AnyType> node=nodes[i].firstChild;
			while(node!=null){
				list.add(node.child);
				node=node.nextChild;
			}
		}
		return list;
	}
	
	public static void main(String[] args) {
		ChildrenTree<String> c=new ChildrenTree<String>();
		Scanner scanner = new Scanner(System.in);
		System.out.println("请输入该树的结点的个数：");
		c.n = scanner.nextInt();
		c.nodes = new PTListNode[c.n];
		System.out.println("请输入" + c.n + "个双亲结点的值：");
		
		//将节点和其序号存入map
		HashMap<String,Integer> map=new HashMap<String,Integer>();
		//创建双亲结点
		for (int i = 0; i < c.n; i++){
			String str1=scanner.next();
			c.nodes[i] = new PTListNode<String>(str1);
			map.put(str1, i);
		}
		//创建孩子结点
		for(int i=0;i<c.n;i++){
			System.out.println("请输入以"+c.nodes[i].data+"为双亲结点的孩子结点，以‘#’结束所有其孩子结点的输入(请逆序输入)");
			int idx=0;
			String str2;
			while(!(str2=scanner.next()).equals("#")){
				idx=map.get(str2);
				CTNode<Integer> node=new CTNode<Integer>(idx);
				node.nextChild=c.nodes[i].firstChild;
				c.nodes[i].firstChild=node;
			}
		}
		
		/*
A B C D E F G H I J
		*/
		
/*
D C B #
F E #
G #
J I H #
*/
		
		//层次遍历结果
		List<Integer> list = new ArrayList<Integer>();
		System.out.println("层次遍历的结果为：");
		list=c.levelOrder(c.nodes);
		Iterator itr=list.iterator();
		
		while(itr.hasNext()){
			int num=(int) itr.next();
			for(String s : map.keySet()){
				if(num==(int)map.get(s)){
					System.out.println(s);
				}
			}
		}
	}
}

/**
 * 双亲结点
 * */
class PTListNode<AnyType> {
	AnyType data;
	CTNode<AnyType> firstChild;

	public PTListNode(AnyType data) {
		this.data = data;
		firstChild = null;
	}
}

/**
 * 孩子结点
 * */
class CTNode<AnyType> {
	int child;
	CTNode<AnyType> nextChild;

	public CTNode(int child) {
		this.child = child;
		nextChild = null;
	}
}

